package com.leetcode.根据数据结构分类.并查集;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2021/1/11
 * @description: 1202. 交换字符串中的元素
 * https://leetcode-cn.com/problems/smallest-string-with-swaps/
 */
public class B_1202_交换字符串中的元素_Retry {

	/**
	 * 在 {@link B_1202_交换字符串中的元素} 上进行优化：
	 * UnionFind + 二叉堆
	 *
	 * @param s
	 * @param pairs
	 * @return
	 */
	public String smallestStringWithSwaps4Mine(String s, List<List<Integer>> pairs) {
		int len = s.length();
		if (len == 1) {
			return s;
		}

		InnerUnionFind unionFind = new InnerUnionFind(len);
		for (int i = 0; i < pairs.size(); i++) {
			unionFind.union(pairs.get(i).get(0), pairs.get(i).get(1));
		}
		char[] charArray = s.toCharArray();
		//直接使用 小顶堆
		HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
		for (int i = 0; i < len; i++) {
			int root = unionFind.find(i);
			if (map.containsKey(root)) {
				map.get(root).offer(charArray[i]);
			} else {
				PriorityQueue<Character> minHeap = new PriorityQueue<>();
				minHeap.offer(charArray[i]);
				map.put(root, minHeap);
			}
		}

		StringBuilder stringBuilder = new StringBuilder();
		for (int i = 0; i < len; i++) {
			//找到 集合代号
			int root = unionFind.find(i);
			//从集合中弹出最小的值
			stringBuilder.append(map.get(root).poll());
		}
		return stringBuilder.toString();

	}

	/**
	 * 没想到路径压缩+ 按秩 排序即使 秩不准确，但是优化好了很多！
	 * 从 【超出时间限制】 -> 59ms！！！
	 */
	class InnerUnionFind {
		//index
		int[] parents;
		private int[] rank;

		public InnerUnionFind(int capacity) {
			this.parents = new int[capacity];
			this.rank = new int[capacity];
			for (int i = 0; i < capacity; i++) {
				this.parents[i] = i;
				this.rank[i] = 1;
			}
		}

		/**
		 * 在并查集中查找 index 下的根节点，并做 Path Compression
		 *
		 * @param index
		 * @return
		 */
		public int find(int index) {
			if (index != parents[index]) {
				parents[index] = find(parents[index]);
			}
			return parents[index];
		}

		/**
		 * @param index1
		 * @param index2
		 */
		public void union(Integer index1, Integer index2) {
			int p1 = find(index1);
			int p2 = find(index2);
			if (p1 == p2) {
				return;
			}
			//否则挂在 p2 上
//			parents[p1] = p2;

			if (rank[p1] == rank[p2]) {
				parents[p1] = p2;
				// 此时以 rootY 为根结点的树的高度仅加了 1
				rank[p2]++;
			} else if (rank[p1] < rank[p2]) {
				parents[p1] = p2;
				// 此时以 rootY 为根结点的树的高度不变
			} else {
				// 同理，此时以 rootX 为根结点的树的高度不变
				parents[p2] = p1;
			}
		}
	}

	public static void main(String[] args) {
		String s = "dcab";
		List<List<Integer>> pairs = new ArrayList<>();
		List<Integer> t1 = new ArrayList<>();
		List<Integer> t2 = new ArrayList<>();
		List<Integer> t3 = new ArrayList<>();
		t1.add(0);
		t1.add(3);
		t2.add(1);
		t2.add(2);
		t3.add(0);
		t3.add(2);
		pairs.add(t1);
		pairs.add(t2);
		//pairs.add(t3);

		B_1202_交换字符串中的元素_Retry action = new B_1202_交换字符串中的元素_Retry();
		String res = action.smallestStringWithSwaps4Mine(s, pairs);
		System.out.println("res = " + res);
	}
}
